class Solution {
public:
    int countSubstrings(string s) {
        string ss;
        for(int i = 0;i < s.size();i++){
            ss += '#';
            ss += s[i];
        }
        ss += '#';
        vector<int> p(ss.size(),1);
        int r = 0;
        int c = 0;
        for(int i = 1;i < ss.size();i++){
            if(i < r){
                p[i] = min(r - i,p[2 * c - i]);
            }else{
                p[i] = 1;
            }
            while(i-p[i]>=0&&i+p[i]<ss.size()&&ss[i-p[i]]==ss[i+p[i]]){
                p[i]++;
            }
            if(i + p[i] > r){
                c = i;
                r = i + p[i];
            }
        }
        int ret = 0;
        for(int i = 0;i < ss.size();i++){
            if(ss[i] == '#'){
                ret += (p[i] - 1) / 2;
            }else{
                ret += 1 + (p[i] - 1) / 2;
            }
        }
        return ret;
    }
};
